package data_structures_and_algorithms.recursion_traceback;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/**
 * @ClassName _784_letterCasePermutation
 * @Description: 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
 *
 * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：s = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 * 示例 2:
 *
 * 输入: s = "3z4"
 * 输出: ["3z4","3Z4"]
 *  
 *
 * 提示:
 *
 * 1 <= s.length <= 12
 * s 由小写英文字母、大写英文字母和数字组成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/letter-case-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: myl
 * @create_time: 2022/10/23 01:18
 */
public class _784_letterCasePermutation {

    public static void main(String[] args) {
        String s = "22c";
        List<String> strings = new _784_letterCasePermutation().letterCasePermutation(s);
        System.out.println(Arrays.toString(strings.toArray()));

    }

    List<String> list = new LinkedList<>();
    public List<String> letterCasePermutation(String s) {
        return letterCasePermutationSolution(s);
    }

    public List<String> letterCasePermutationSolution(String s) {
        char[] chars = s.toCharArray();
        backtrace(chars, 0);
        return list;
    }

    public void backtrace(char[] chars, int index){
        // 注意边界的取值，这里需要取到末尾的后一位，表示所有的位置元素都处理完了
        if (index == chars.length){
            list.add(new String(chars));
            return;
        }

        while (!isChar(chars[index])){
            index++;
            if (index == chars.length){
                list.add(new String(chars));
                return;
            }
        }
        // 转换字符
        convertChar(chars, index);
        backtrace(chars, index + 1);
        convertChar(chars, index);

        // 不转换字符
        backtrace(chars, index+1);
    }

    public boolean isChar(char c){
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
            return true;

        return false;
    }

    public void convertChar(char[] chars, int index){
        // 判断属于小写字母 or 大写字母
//        if (chars[index] >= 'a' && chars[index] <= 'z'){
//            // 小写字母
//            chars[index] = (char) (chars[index] - 32);
//        }else {
//            chars[index] = (char) (chars[index] + 32);
//        }


        // 这里优化下转换方法：1、可以使用API接口；2、手工计算（使用位运算）
        // 调用接口
//        if (chars[index] >= 'a' && chars[index] <= 'z'){
//            // 小写字母
//            chars[index] = Character.toLowerCase(chars[index]);
//        }else {
//            chars[index] = Character.toLowerCase(chars[index]);
//        }

        // 位运算方式
        chars[index] ^= (1<<5);// 自己在本子上演算下，就是这么个结果
    }







}
